package Offer;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/*
    请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，
    第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

    思路：
        主要是利用双端队列可以从两边进行插入删除的特性
        可以用LinkedList双端队列的数据结构
        对于奇数层的使用add添加到队列中，然后使用removeFirst来达到正序输出的目的
        对它的下一层先左孩子后右孩子，使用addLast添加到队列中
        输出偶数层的过程：通过removeLast来达到逆序输出的目的
        对于它的下一层，先右孩子后左孩子，addFirst添加到队列中
* */
public class T32III_levelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root==null){
            return new ArrayList<>();
        }
        Deque<TreeNode> queue = new LinkedList<>();     //队列
        List<List<Integer>> res = new ArrayList<>();    //存储结果
        queue.add(root);

        while (!queue.isEmpty()) {
            //先打印奇数层(从左向右)
            ArrayList<Integer> item = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.removeFirst();
                item.add(node.val);

                //不一定要先左后右，也可以是先右后左，这样出队的时候就得用removeFirst(反正原则就是在一端remove就要在另外一端add)
                if (node.left != null) {
                    queue.addLast(node.left);
                }
                if (node.right != null) {
                    queue.addLast(node.right);
                }
            }
            if (item.size() != 0) {
                res.add(item);
            }

            if (queue.isEmpty()) {
                break;
            }

            //接着打印偶数层
            item = new ArrayList<>();
            for (int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.removeLast();
                item.add(node.val);
                if (node.right != null) {   //这里是先right再left(不要写成left再right)
                    queue.addFirst(node.left);
                }
                if (node.left != null) {
                    queue.addFirst(node.left);
                }
            }
            if (item.size() != 0) {
                res.add(item);
            }
        }
        return res;
    }
}
